package Test;

import java.util.Arrays;

class MyHashMap{

   private Node[] array;
   private int size = 0;
    class Node {
        final int key;
        int value;
        Node next;
        public Node(int key, int value) {
            this.key = key;
            this.value = value;
        }
    }

    //一般负载因子不可以改变，所以这里用 static final
    public static final double DEFAULT_LOAD_FACTOR=0.75;
    //提供两个构造方法,一个指定大小,一个默认大小
    public MyHashMap() {
        array =  new Node[16];
    }
    public MyHashMap(int n){
        array =  new Node[n];
    }
    public void put(int key,int value){
        int length = array.length;
        //添加结点需要求出该结点的hash值
        int hash = key % length;
        Node node;
        if ((node = array[hash]) == null){
            //如果当前数组的hash对应的下标为空就直接添加
            array[hash] = new Node(key,value);
        }else {
            //此时next不为空,那就for循环尾插
            while (true){
                //需要判断是否key值一样,如果一样就修改
                if(node.key == key){
                    node.value = value;
                   return;
                }
                //把if放在这里是因为这样可以保证每个结点的key值都进行了上述if操作,
                //while(node.next != null) 如果将这个代码替换上面的while(true)
                //那么当node.next为null时就会直接退出循环,此时的node还没有进行对比操作呢,就可能会出现错误
                if(node.next == null){
                    //所有结点对比完退出循环
                    break;
                }
                //不断向后next
                node = node.next;
            }
            //到这里此时的Node的下一个结点为空,且没有key值相同的结点
            node.next = new Node(key,value);

        }
        size++;
        if(loadFactor()){
            //负载因子>0.75后就扩容
            resize();
        }
    }

    //扩容方法
    //这里的链表扩容依旧选择的是尾插,头插容易实现,各位看自己喜好,jdk1.8的HashMap是采用尾插的
    private void resize() {
    long newLength = array.length* 2L;
        if(newLength > Integer.MAX_VALUE){
            newLength = Integer.MAX_VALUE;
        }
            //如果要扩容的长度超过了int的最大长度,就将要扩容的长度改为Integer.MAX_VALUE(即2^31-1)
            Node[] newArray = new Node[(int) newLength];//
            //现在开始扩容
        for (Node value : array) {
            Node node = value;
            while (node != null) {//node为空说明该结点的链表都遍历完了,可以进行下一个链表的拷贝
                Node nodeNext = node.next;
                //由于后续操作会将node的下一个结点丢失,
                // 所以需要设置个遍历记录node的下一个结点
                //将node这个链表的所有元素添加到新的哈希表里
                //求出hash值,将这些结点按照新的哈希值放入新的位置
                int hash = node.key % array.length;
                Node newNode;
                if ((newNode = newArray[hash]) == null) {
                    //如果为空就直接把该节点添加到新数组下标对应的位置
                    newArray[hash] = node;
                } else {
                    //如果不为空就向后next
                    while (newNode.next != null) {
                        newNode = newNode.next;
                    }
                    //此时newNode的下一个结点为空,进行尾插
                    newNode.next = node;
                }
                //由于node可能后面还有结点,所以需要将node.next置为null
                node.next = null;
                //通过nodeNext找到node的下一个结点
                node = nodeNext;
            }
        }
        array = newArray;
    }
    public int get(int key){
        //根据key值返回对应的value
        int hash = key % array.length;
        Node node;
        if((node = array[hash]) == null){
            return -1;
        }
        //到这里说明这个hash值下标对应的数组元素存在
        while (node != null){
            if(node.key == key){
                return node.value;
            }
            node = node.next;
        }
        //如果为空了还没有找到对应的就返回-1
        return -1;
    }
    private boolean loadFactor() {
        //×1.0是为了把size变成double类型
        return 1.0*this.size/array.length > 0.75;
    }
    public int size(){
        return size;
    }

    public void print() {
        for (int i = 0; i < array.length; i++) {
            Node node = array[i];
            if(node != null){
                StringBuilder builder = new StringBuilder();
            while (node != null){
                builder.append("key:"+node.key+" val:"+node.value+" ");
                node = node.next;
            }
            System.out.println(builder);
            }
        }
    }
}

public class Test9 {
    public static void main(String[] args) {
        MyHashMap map = new MyHashMap();
        map.put(666,1);
        map.put(777,1);
        map.put(888,1);
        map.put(999,1);
        map.put(999,2);
        map.put(999,3);
        map.put(999,4);
        map.put(999,5);
        System.out.println(map.get(666));
        map.print();

    }

}
